package algorithm;

import java.util.Random;

public class leetcode_0528 {
    class Solution {

        int[] pre;
        int max;

        public Solution(int[] w) {
            pre = new int[w.length];
            pre[0]=w[0];
            for(int i=1;i<w.length;++i){
                pre[i]= pre[i-1]+w[i];
            }
            max = pre[pre.length-1];
        }

        public int pickIndex() {
            Random random = new Random();
            int nextInt = random.nextInt(max);
            return binarySearch(pre,nextInt+1,0,pre.length-1);
        }

        public int binarySearch(int[] pre , int target,int left,int right){
            if(left==right) return left;
            int mid = left + (right-left)/2;
            if(pre[mid]==target) return mid;
            if(pre[mid]<target){
                return binarySearch(pre,target,mid+1,right);
            }
            return binarySearch(pre,target,left,mid);
        }
    }
}
